package name.huzhenbo.java.algorithm.graph;

import java.util.HashSet;
import java.util.Set;

class ArticuFinder {
    private Graph graph;
    private int[] visited;
    private int count;
    private int[] low;
    private static Set<Integer> founds;


    public ArticuFinder(Graph graph) {
        this.graph = graph;
        visited = new int[graph.vertexNum()];
        low = new int[graph.vertexNum()];
        founds = new HashSet<Integer>();
    }

    public void find() {
        for (int i = 0; i < graph.vertexNum(); i++) {
            if (visited[i] == 0) {
                dFSArticu(i);
            }
        }
    }

    // DSF travese
    // the low[start] = min {visited[start], low[w], visited[v]}
    // where w is the child of start during dfs traverse
    // v is start's ancestor, who is linked back from v.
    private void dFSArticu(int start) {
        // 1. visited[start]
        int min = visited[start] = ++count;
        for (int w = graph.firstAdjVex(start); w >= 0; w = graph.nextAdjVex(start, w)) {
            if (visited[w] == 0) {
                // 2. low[w], where w is the children of start in traversal tree, because w is not visited yet.
                // get low[w] through recursive
                dFSArticu(w);
                if (low[w] < min) min = low[w];

                // if found any children has the bigger low than start, then start is the articulation point.
                if (low[w] >= visited[start]) foundArticu(start);
            } else if (visited[w] < min) {
                // 3. visited[v], v is the acestors of start in dfs traversal tree, because it's already visited.
                min = visited[w];
            }
        }
        low[start] = min;  // low[start] = min{visited[start], low[w], visited[v]}
    }

    private static void foundArticu(int i) {
        if(founds.contains(i)) return;
        founds.add(i);
        System.out.println("Articulation point: " + i);
    }

}
